BZOJ1100【POI2007】对称轴osi < Manacher >

Problem

【POI2007】对称轴osi

Description

小朋友——一个闻名遐迩的年轻数学家——有一个小MM，。小朋友非常喜欢他的MM，所以他很乐意帮助他的MM做数学作业。但是，就像所有科学的容器一样，FGD的大脑拒绝不停地重复思考同样的问题。不幸的是，是一个十分用功的学生，所以她不停地让帮助她检查她的作业。
一个阳光明媚的周末，的数学老师布置了非常多的寻找多边形的对称轴的题，足够她做相当长的一段时间了。在此之前已经决定去海边度过这个难得的假期，不过他还是觉得应该帮助他的MM对付可爱的数学作业。很快地，他找到了解决方案，最好写一个程序来帮助检查她的数学作业。
因为并非一个计算机科学家，所以他找到了他的好朋友你，请你帮助他完成这个任务。
请写一个程序：读入多边形的描述计算出每个多边形的对称轴数将计算的结果输出。

Input

输入的第一行包含一个正整数，为多边形的边数。
接下来，为个多边形的描述。
每个描述的第一行为一个正整数，表示了多边形的点数。
后面行每行两个整数和，依次表示多边形的顶点坐标。
多边形不一定是凸的，但是不自交。任何两条边都只有最多一个公共点，即它们的公共端点。此外，没有两条连续的边平行。

Output

你的程序应该输出正好行，第k行包含了一个整数——表示第个多边形有多少个对称轴。

Sample Input

Sample Output

1
2

4
2

标签：Manacher

Solution

好题。

如果我们确定一个多边形的每条边和每个角，我们就确定了这个多边形。那么半个多边形呢？也是一样的。
我们将边形写成长为的数组，即每条边的长度和两边夹角的叉积交错排列。将这个数组看成一个环，对称意味着这个环关于某个位置对称。按常理断环成链后跑，过程中判每个位置的回文半径是否大于即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, nxt[MAX_N+5], s[MAX_N+5]; bool mrk[26];
int main() {
    read(n);
    for (int i = 0; i < n; i++) read(nxt[i]), nxt[i] = i-nxt[i];
    for (int p = 1; p < n; p++) {
        if (~nxt[p]) s[p] = s[nxt[p]];
        else {
            memset(mrk, false, sizeof mrk);
            for (int q = nxt[p-1]; ~q; q = nxt[q])
                mrk[s[q+1]] = true;
            for (int c = 1; c < 26; c++)
                if (!mrk[c]) {s[p] = c; break;}
        }
    }
    for (int i = 0; i < n; i++) printf("%c", 'a'+s[i]);
    return 0;
}